package progect_01;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Graph {
	
	private ArrayList<String> GraphNode;//用于存放图的结点
	private int[][] edges;//用于存放图的邻接矩阵
	private int edgeNum;//用于存放图的边的数量
	private boolean[] JudgeIfVisited;
	
	public static void main(String[] args) {
		int n=7;
		Graph graph=new Graph(n);
		String[] nodeStrings= {"A","B","C","D","E","F","G"};
		//循环插入节点
		for(String value:nodeStrings) {
			graph.InsertNode(value);
		}
		//        0   1 0  2  1  2 1  3  1  4        5  6
		//连接边   A->B A->C  B->C B->D  B->E,不连通：F->G
		graph.LinkEdges(0, 1, 1);
		graph.LinkEdges(0, 2, 1);
		graph.LinkEdges(1, 2, 1);
		graph.LinkEdges(1, 3, 1);
		graph.LinkEdges(1, 4, 1);
		graph.LinkEdges(5, 6, 1);
		//显示图的矩阵
		//graph.ShowEdges();
		System.out.println("深度优先搜索：");
		graph.DFS();
		System.out.println();
		System.out.println("广度优先搜索：");
		graph.BFS();
	}
	//构造器
	public Graph(int n) {
		//初始化
		GraphNode=new ArrayList<String>(n);
		edges=new int[n][n];
		edgeNum=0;//初始化与不初始化都行，因为默认就是0
		JudgeIfVisited=new boolean[n];//布尔数组默认初始化值是false
		
		
	}
	
	
	//获取第一个邻接结点（第一个为1的结点）
	public int GetFristNode(int index) {
		//可以简单描述为获取邻接矩阵每行第一个为1的那个节点的下标
		for(int i=0;i<GetNodeNum();i++) {
			if(edges[index][i]==1) {
				return i;//index为行的第一个1--》也就是第一个邻接结点
			}
		}
		return -1;
		
	}
	//获取下一个邻接结点
	public int GetFirstNextNode(int index1,int index2) {
		//比如此时A->B->C,(B->C,B->D,B-E)
		//如果此时走到C发现没路了，就会回退到B，走B的D路（C的下一个位置就是D），这就是这个方法的作用
		//再简单描述就是获取回退路里的被访问过的结点的位置的下一个未被访问过的结点的位置。
		for(int i=index2+1;i<GetNodeNum();i++) {
			if(edges[index1][i]==1) {
				return i;
			}
		}
		return -1;
		
		
	}
	//深度优先遍历算法重载
	public void DFS() {
		Arrays.fill(JudgeIfVisited, false);
		//考虑非连通图
		for(int i=0;i<GetNodeNum();i++) {
			if(!JudgeIfVisited[i]) {
				//没有访问过的结点
				DFS(i);
			}
		}
	}
	
	//深度优先遍历算法
	public void DFS(int InitIndex) {
		System.out.print(GraphNode.get(InitIndex)+"=>");//先输出第一个结点
		//设置为已访问
		JudgeIfVisited[InitIndex]=true;
		//获取第一个邻接结点的索引01
		int firstNodeIndex=GetFristNode(InitIndex);
		while(firstNodeIndex!=-1) {//说明此时找到了一条路
			//这里使用循环不使用if的原因：
			//如果使用if的话当走A->B这条路的时候就会标记AB已经访问过了，此时在
			//邻接矩阵的B的这行里，会首先判断B->A。此时不满足下面的判断条件了，就会
			//往下继续执行走出最外层的if，但此时结点的路并没有走完。
			if(!JudgeIfVisited[firstNodeIndex]) {
				//说明这个结点还未被访问，这条路可以走
				DFS(firstNodeIndex);
			}
			//结点已经被访问--就要回退到有其他路的前节点，找前节点的下条路
			firstNodeIndex=GetFirstNextNode(InitIndex, firstNodeIndex);
			
		}
	}
	
	//广度优先搜索算法的重载--连通图不连通图都可以输出出来
	public void BFS() {
		Arrays.fill(JudgeIfVisited, false);//调用完深度优先搜索后重新初始化数组
		for(int i=0;i<GraphNode.size();i++) {
			if(!JudgeIfVisited[i]) {
				BFS(i);
			}
		}
	}
	
	
	//广度优先搜索算法--一个结点，只能输出连通图
	public void BFS(int InitIndex) {
		//思路：广度优先搜索算法首先先访问给定的初始节点的索引，然后将这个索引加入到队列中，并同时
		//标记这个结点已经访问，然后再出队，以这个初始节点的索引为行号，扎到这行的第一个1，若是没有访问到
		//就就入队同时将其标记已经访问，若这行的第一个1已经访问l，就要找到这个1的同行的下个为1的邻接结点。
		//如果这行找完了，就继续出队队头的第一个索引，在这行中继续找。
		
		//LinkedList是队列Queue的实现类
		//创建一个队列用于存放结点的索引
		LinkedList<Integer> queue=new LinkedList<Integer>();
		//首先输出初始节点
		System.out.print(GraphNode.get(InitIndex)+"=>");
		//将其标记为已访问
		JudgeIfVisited[InitIndex]=true;
		//入队--队尾入队，队头出队
		queue.addLast(InitIndex);
		
		//循环出队这个过程，也就是矩阵的每行走遍
		while(!queue.isEmpty()) {
			//出队--队头
			int QueueHeadIndex=queue.removeFirst();
			//接下来就是找到这行的索引邻接结点，也就是找到某个结点的所有未被访问的连接边
			int RowFirstIndex=GetFristNode(QueueHeadIndex);
			//循环的找这行中没被访问的边
			while(RowFirstIndex!=-1) {//说明有连接边
				if(!JudgeIfVisited[RowFirstIndex]) {
					//说明没被访问
					//此时就要输出这个结点，然后标记访问，然后入队
					System.out.print(GraphNode.get(RowFirstIndex)+"=>");
					JudgeIfVisited[RowFirstIndex]=true;
					queue.addLast(RowFirstIndex);
				
				}
				//如果已经被访问了，就要找这条边的其他边。也就是找这个1后面的1
				RowFirstIndex=GetFirstNextNode(QueueHeadIndex, RowFirstIndex);//还在这行找
				//把这个RowFirstIndex重新定位为下个为1的索引。
			}
			
		}
		
		
	}
	
	
	
	//插入图的结点
	public void InsertNode(String value) {
		GraphNode.add(value);
	}
	
	//连接结点的边
	public void LinkEdges(int index1,int index2,int weight) {
		//对于无向边而言，A->B 与 B->A 都是连同的，连同就用1来表示
		edges[index1][index2]=1;
		edges[index2][index1]=1;
		edgeNum++;//此时就表示一条边已经连好了
	}
	//返回边的总数
	public int GetEdgesNum() {
		return edgeNum;
	}
	//返回结点的总数
	public int GetNodeNum() {
		return GraphNode.size();
	}
	//输出图的邻接矩阵
	public void ShowEdges() {
		for(int[] edge:edges) {
			System.out.println(Arrays.toString(edge));//输出每一层
		}
	}
	

}


